說明

二元搜尋樹:在節點的兩個分支中，比較節點大小並存入左右

程式碼

#include <stdio.h>
#include <stdlib.h>
typedef struct tree *tree_p;
struct tree {
  int data;
  tree_p left;
  tree_p right;
  tree_p back;
} tree;
tree_p root = NULL, ptr, cur;
tree_p add_node(int num);
void inorder(tree_p root);
void creat(int num);
void basic1();

主程式

int main() {
  basic1();
  inorder(root);
  printf("\n------------執行完成------------\n");
  creat(6);
  printf("\n------------添加節點------------\n");
  inorder(root);
  printf("\n------------執行完成------------\n");
}

函式

void basic1():基本測資

void basic1() {
  creat(4);
  creat(2);
  creat(9);
  creat(1);
  creat(3);
  creat(7);
  creat(5);
  creat(8);
}

void creat(int num):插入節點

進入迴圈判斷，利用迴圈判定大小，不斷向左右節點移動，當下一個節點為空白時，跳出迴圈，並在下一個節點新增。

void creat(int num) {
  ptr = root;
  cur = root;
  if (root == NULL) {
    root = add_node(num);
  } else {
    while (ptr != NULL) {
      cur = ptr;
      if (ptr->data < num) {
        ptr = ptr->right;
      } else if (ptr->data > num) {
        ptr = ptr->left;
      } else {
        printf("same");
      }
    }
    //cur會一直跟在ptr的後一格
    //在存入節點時，判斷大小選擇左右
    if (cur->data < num) {
      cur->right = add_node(num);
      cur->right->back = cur;
      //順便新增back節點指向該節點的前一個位置
    } else {
      cur->left = add_node(num);
      cur->left->back = cur;
    }
  }
}

結果

(中序輸出)